1. Field of the Invention
The present invention is related to the field of circuit design. In particular, the present invention is related to method and apparatus to insert flip-flops in a circuit design.
2. Description of the Related Art
Interconnect optimization is a critical component of circuit design, and in particular, of Very Large Scale Integration (VLSI) circuit design. As part of interconnect optimization of a VLSI circuit design, repeaters (e.g., buffers and inverters) are used to reduce interconnect delay and to meet transition time/noise constraints. However, merely using repeaters does not solve all timing requirements; for example, when wire delay is greater than a clock cycle, the mere addition of repeaters may not solve the timing constraints and the insertion of flip-flops/latches is essential. If the VLSI circuit is deeply pipelined, the number of flip-flops in the circuit is significant and an automated tool to insert flip-flops in the circuit design is necessary to reduce the Register-Transfer-Level (RTL)-to-layout convergence time.
Typically, the RTL specification determines the number of clock cycles required for each driver-receiver path in the design. When data from a driver requires more than one clock cycle to reach a receiver, a flip-flop is typically added to the RTL specification of the circuit design. However, to determine the physical placement of the flip-flops in the VLSI circuit design, an automatic flip-flop insertion method may be necessary to optimize the physical placement of the flip-flops based on the RTL specifications.
Conventional flip-flop insertion methods insert flip-flops in the circuit to meet latency constraints by using heuristic techniques which are sub optimal. FIG. 1 illustrates flip-flops placed in a circuit using a conventional flip-flop insertion method. FIG. 1 illustrates a circuit 100 having two branches wherein each branch has a sink node (receiver) s1 and s2 respectively and a source node (driver) vd to drive the sink nodes s1 and s2. The RTL specification provides the required arrival times (treq) at s1 and s2 as t1 and t2 pico seconds (psec) after the positive edge of a clock, and also provides the time period of the clock (tc) that drives the source node vd. In addition, the RTL specification provides additional constraints e.g., limiting one flip-flop on the path p(vd, s1) from the driver vd to the receiver s1, and limiting 2 flip-flops on the path p(vd, s2) from the driver vd to the receiver s2. As FIG. 1 illustrates, a conventional flip-flop insertion method places a flip-flop F on path p(vd,s1) at t1 psec away from s1 and t2 psec away from s2 on path p(vd,s2). In accordance with the constraint requirements, a second flip-flop F is placed a clock cycle, tc psec, away from the first flip-flop on path p(vd,s2) toward the driver before branch junction 105. Thus, conventional flip-flop insertion methods place flip-flops in the circuit by utilizing the required arrival time constraint given at the receiver to fix the position of the last flip-flop on the path from the driver to the receiver, and subsequent flip-flops, if specified, are placed a clock cycle away between flip-flops. This causes the positive margin if any (i.e., the net positive time differential between treq and the actual arrival time tarr) to accumulate at the driver vd with no margin at the receivers s1 and s2. Having positive margins accumulate at the driver or at the intermediate flip-flops between the driver and the receiver is inefficient as the positive margins are unavailable for circuit design, particularly if time constraints at the receiver are critical.
Example embodiments of the present invention are illustrated in the accompanying drawings. The accompanying drawings, however, do not limit the scope of the present invention. Similar references in the drawings indicate similar elements.